{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "梯度提升决策树（Gradient Boosting Decision Tree-GBDT）是梯度提升方法（GB）和决策树算法的结合，它是Boosting族中一个重要的算法，有很多简称，如GBT（Gradient Boosting Tree）, GTB（Gradient Tree Boosting ）， GBRT（Gradient Boosting Regression Tree）, MART(Multiple Additive Regression Tree)。基于梯度提升算法的学习器叫做GBM(Gradient Boosting Machine)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "疑问：\n",
    "1. 如何初始化弱学习器\n",
    "2. 如何理解负梯度的计算公式\n",
    "3. 如何利用$(x_i,r_{ti}) \\quad (i=1,2,...,m)$拟合一颗CART回归树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GBDT回归算法流程\n",
    "GBDT使用的是M颗树组成的加法模型\n",
    "$$F(x,\\omega)=\\sum_{m=0}^M \\alpha_m h_m(x,\\omega_m)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "输入：\n",
    "- 训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$，其中$x_i \\in \\chi \\subseteq R^n$，$y_i \\in Y \\subseteq R$\n",
    "- 损失函数$L(y,f(x))$\n",
    "\n",
    "输出：最终回归树$f_M$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 初始化弱学习器$f_0(x)$\n",
    "$$f_0(x)=arg \\ min_c \\sum_{i=1}^ML(y_i,c)$$\n",
    "    - 初始的弱学习器在笛卡尔坐标系下就是平行于x轴的一条直线\n",
    "2. $对m=1,2,...,M$  # 建立$M$颗回归树\n",
    "    1. 对$i=1,2,...,N$，计算第$m$颗树的响应值（损失函数的负梯度，即伪残差）  **# 如何理解该式？**\n",
    "    $$r_{mi}=-\\left [ \\frac{\\partial L(y_i,f(x_i))}{\\partial f(x_i)} \\right ] _{f(x)=f_{m-1}(x)}$$\n",
    "        - **特别地，若采用平方损失函数$L(y_i,f(x_i))=\\frac{1}{2}(y_i-f(x_i))^2$，$r_{mi}=y_i-f(x_i)$，即残差**\n",
    "    2. $对i=1,2,...,N$，使用CART回归树拟合数据$(x_i,r_{mj})$,得到第$m$颗回归树，其对应叶结点区域为$R_{mj}$， $j=1,2,...,J$，$J$为第$m$颗树的叶结点的总数。  \n",
    "        - 步骤B生成了一颗带叶结点的回归树，但各叶结点的最终输出还需要拟合（由步骤C实现）\n",
    "        - **疑问：为何训练时要将$r_{mj}$作为标签值？**\n",
    "        - 求回归树的方法：同CART回归树的生成方法\n",
    "    3. 对$J$个叶节点区域$j=1,2,...,J$，计算出使得拟合效果最好的参数$c_{mj}$ $$c_{mj}=arg \\ min_c \\sum_{x_i \\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$$\n",
    "        - **参数$c_{mj}$的含义**：若采用平方损失函数，对于第$m$颗树，为每个叶子节点分别赋一个参数$c_{mj}$，来拟合残差\n",
    "        - 求参数的方法：求一阶导数\n",
    "    4. 更新强学习器$$f_m(x)=f_{m-1}(x)+\\sum_{j=1}^J c_{mj}I(x \\in R_{mj})$$\n",
    "3. 得到强学习器$$f_M(x)=f_0(x)+\\sum_{m=1}^M\\sum_{j=1}^Jc_{mj}I(x \\in R_{mj})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**小结**：\n",
    "- GBDT回归算法中，要预设的参数：\n",
    "    - 学习率（正则化项）\n",
    "    - CART树深度\n",
    "    - 迭代次数（基学习器总数）\n",
    "- GBDT回归算法中，要学习内容：\n",
    "    - 初始弱学习器\n",
    "    - 每轮迭代中要学习的内容：\n",
    "        - 第m个回归树（的结构，即叶结点区域）\n",
    "        - 第m个学习器的参数$c_{mj}, \\ j=1,2,...,J$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GBDT回归常用的损失函数\n",
    "sklearn实现了4种损失函数：\n",
    "- 均方误差（默认）：'ls'。适合噪音不多的情况。\n",
    "- 绝对值损失：'lad'。\n",
    "- Huber损失：'huber'。适合噪音较多的情况。\n",
    "- 分位数损失：'quantile'。适合需要对训练集分段预测时。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 均方误差$$L(y_i,f(x_i))=(y_i-f(x_i))^2$$\n",
    "对应的负梯度为$$y_i-f(x_i)$$\n",
    "\n",
    "2. 绝对值损失$$L(y_i,f(x_i))=|y_i-f(x_i)|$$\n",
    "对应的负梯度为$$sign(y_i-f(x_i))$$\n",
    "\n",
    "3. Huber损失"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GBDT二分类算法流程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GBDT常用损失函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GBDT的正则化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GBDT的优缺点\n",
    "主要优点\n",
    "1. 可以灵活处理各种类型的数据，包括连续值和离散值。\n",
    "2. 在相对少的调参时间情况下，预测的准确率也可以比较高。这个是相对 SVM 来说的。\n",
    "3. 使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber 损失函数和 Quantile 损失函数。\n",
    "\n",
    "主要缺点\n",
    "1. 由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的 SGBT 来达到部分并行。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
